Hidden In Plain Sight 9: The Physics Of Consciousness by Thomas Andrew

Author:Thomas, Andrew [Thomas, Andrew]
Language: eng
Format: epub
Published: 2018-02-24T16:00:00+00:00

Turing proposed that that piece of code — which performs the halting test — could then be included as part of the following program:

You will see from the flowchart that if the input program does not halt, then the flowchart halts. But if the input program does halt, then the program loops forever, i.e., it never halts.

So we can see from the flowchart that the behaviour of the flowchart algorithm is precisely the opposite of the behaviour of the input program. If the input program does not halt then the flowchart algorithm does halt. But if the input program does halt then the flowchart algorithm does not halt. As I said, the behaviour of the flowchart algorithm is precisely the opposite of the input program.

Alan Turing then did something ingenious. He took the flowchart algorithm (which can be coded as a computer program) and presented it as input to itself! Turing then asked the question: "Does the resulting program — given itself as input — halt or loop forever?"

There are two possibilities. If the input program does halt then — according to the algorithm — the flowchart algorithm does not halt and so the input program does not halt. Conversely, if the input program does not halt then — according to the flowchart — the flowchart algorithm does halt and so the input program does halt.

So if the input program does halt then it does not halt, and if the input program does not halt then it does halt. As in the liar's paradox, the self-referential nature of Turing's method has created a paradox.

A paradox is a situation which cannot exist: a computer program has to either halt or not halt — it can't do both. The only conclusion we can make is that the general halting tester program — the piece of code in the diamond — cannot exist. This method which Turing used in his proof is called "proof by contradiction".

Turing had therefore solved the question of the halting problem: it could never be possible to write a general algorithm which could determine if any other program either halted or looped forever.

Turing published his solution in 1937 in Proceedings of the London Mathematical Society . This was a magnificent achievement by Turing, and it established his reputation as a top-rank mathematician.

The implications for the android brain, however, are not so appealing. The result suggests that if we have a computer brain then there will always be a problem (the halting problem being an example) for which it is known that there is a solution (a program will definitely either halt or not halt) but the computer brain cannot calculate that solution. The solution is then said to be uncomputable .

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.